// Created by WXX on 2021/10/22 20:03
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>> &a, vector<int> &b) {

        vector<vector<int>> res;

        int k = 0;
        while (k < a.size() && a[k][1] < b[0]) res.push_back(a[k++]);  // 左侧无交集的部分

        if (k < a.size()) {
            b[0] = min(b[0], a[k][0]);
            while (k < a.size() && a[k][0] <= b[1]) b[1] = max(b[1], a[k++][1]);
        }
        res.push_back(b);

        while (k < a.size()) res.push_back(a[k++]);  // 右侧无交集的部分

        return res;
    }
};

void OutputBasicArray2D1(vector<vector<int>> nums) {

    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        cout << "[";
        for (int j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ", ";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {

    vector<vector<int>> intervals = {{1,  2},
                                     {3,  5},
                                     {6,  7},
                                     {8,  10},
                                     {12, 16}};
    vector<int> newInterval = {4, 8};
    OutputBasicArray2D1(Solution().insert(intervals, newInterval));

    return 0;
}
